package com.lfg.leetcode.leetcode1000;


import java.util.Arrays;

public class No1134findTheCity {
    public static void main(String[] args) {
//        System.out.println(findTheCity2(6, new int[][]{{0, 1, 10}, {0, 2, 1}, {2, 3, 1}, {1, 3, 1}, {1, 4, 1}, {4, 5, 10}}, 20));
        System.out.println(findTheCity(5, new int[][]{{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}}, 2));
        System.out.println(findTheCity(4, new int[][]{{0,1,3}, {1,2,1}, {1,3,4}, {2,3,1}}, 4));
    }
    // 5- 4,10 - 1,9 -3,8 -2,7 - 0,6


    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {

        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(map[i], Integer.MAX_VALUE);
            map[i][i] = 0;
        }
        for (int[] array : edges) {
            map[array[0]][array[1]] = array[2];
            map[array[1]][array[0]] = array[2];
        }

        int minNode = Integer.MAX_VALUE;
        int ret = -1;
        for (int i = 0; i < n; i++) {
            int[] visited = new int[n];
            int[] dis = new int[n];

            System.arraycopy(map[i], 0, dis, 0, n);

            for (int a = 0; a < n; a++) {
                int min = Integer.MAX_VALUE;
                int start = 0;

                for (int j = 0; j < n; j++) {
                    if (i != j && visited[j] == 0 && dis[j] < min) {
                        min = dis[j];
                        start = j;
                    }
                }
                visited[start] = 1;
                for (int j = 0; j < n; j++) {
                    if (i == j || j == start) {
                        continue;
                    }
                    if (map[start][j] == Integer.MAX_VALUE) {
//                        dis[j] = dis[start];
                        continue;
                    }
                    int num = dis[start] + map[start][j];
                    if (visited[j] == 0 && dis[j] > num) {
                        dis[j] = num;
                    }
                }
            }
            int count = 0;
            for (int k = 0; k < n; ++k) {
                if (dis[k] <= distanceThreshold) {
                    ++count;
                }
            }
            if (count <= minNode) {
                minNode = count;
                ret = i;
            }
        }
        return ret;
    }


    public static int findTheCity2(int n, int[][] edges, int distanceThreshold) {
        int[] mark = new int[n];//记录小于distanceThreshold的邻居城市个数
        //1.创建邻接矩阵
        final int N = Integer.MAX_VALUE;
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = N;
            }
        }
        for (int[] p : edges) {
            graph[p[0]][p[1]] = p[2];
            graph[p[1]][p[0]] = p[2];
        }

        //2.floyd算法
        int len = 0;
        for (int k = 0; k < n; k++) {//中间结点
            for (int i = 0; i < n; i++) {//开始结点
                for (int j = 0; j < n; j++) {//结尾结点
                    if (i == j || graph[i][k] == N || graph[k][j] == N) continue;//跳过一些不满足的情况
                    len = graph[i][k] + graph[k][j];
                    graph[i][j] = Math.min(len, graph[i][j]);
                }
            }
        }

        //3.每个城市距离不大于distanceThreshold的邻居城市的数目
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] <= distanceThreshold) {
                    mark[i]++;
                }
            }
        }
        //4.找数目少，编号最大的
        int min = n;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (min >= mark[i]) {
                min = mark[i];
                ans = i;
            }
        }

        return ans;
    }

}



